package LC;

/**
 * @author lhn
 * @date 2024-09-20 17:06
 * 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
 */

public class JumpGame {
    public static void main(String[] args) {
        int[] nums1 = {2, 3, 1, 1, 4};
        System.out.println(canJump_m1(nums1));

        int[] nums2 = {2, 0};
        System.out.println(canJump_m1(nums2));

        int[] nums3 = {0};
        System.out.println(canJump_m2(nums3));
    }
    private static boolean[] visited;
    public static boolean canJump_m1(int[] nums) {
        int n = nums.length;
        visited = new boolean[n];
        return dfs(nums, 0);
    }

    private static boolean dfs(int[] nums, int index) {
        // 如果已经到达最后一个下标，则返回true
        if (index + nums[index] >= nums.length - 1) {
            return true;
        }

        // 如果当前位置已经被访问过，或者无法从当前位置继续跳跃，则返回false
        if (visited[index] || nums[index] == 0) {
            return false;
        }

        visited[index] = true; // 标记当前位置为已访问

        // 尝试从当前位置向后跳跃，并递归地检查是否可以从下一个位置到达终点
        for (int i = 1; i <= nums[index]; i++) {
            if (dfs(nums, index + i)) {
                return true;
            }
        }

        return false; // 如果所有可能的跳跃都无法到达终点，则返回false
    }

    public static boolean canJump_m2(int[] nums) {
        int maxReached = 0;  // 表示当前能到达的最远位置
        for (int i = 0; i < nums.length - 1; i++) {
            if (i > maxReached) return false;    //可到达的边界小于当前位置，则无法到达
            maxReached = Math.max(maxReached, i + nums[i]);
        }
        return true;
    }
}
